/**
 * @Author: linzp
 * @Date: 2022/07/14/11:27
 */
public class demo0714 {
    public static void main(String[] args) {

    }

    /**
     * 69. x 的平方根
     * 给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
     * <p>
     * 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
     * <p>
     * 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
     * <p>
     * <p>
     * <p>
     * 示例 1：
     * <p>
     * 输入：x = 4
     * 输出：2
     * 示例 2：
     * <p>
     * 输入：x = 8
     * 输出：2
     * 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
     */
    public int mySqrt(int x) {
        int left = 0, right = x;
        int res = -1;
        while (left <= right) {
            int mid = left + ((right - left) >> 2);
            if ((long)mid * mid <= x) {//加long防止太长了越界
                left = mid + 1;
                res = mid;
            } else {
                right = mid - 1;
            }
        }
        return res;
    }

    /**
     * 367. 有效的完全平方数
     * 给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
     *
     * 进阶：不要 使用任何内置的库函数，如  sqrt 。
     *
     *
     *
     * 示例 1：
     *
     * 输入：num = 16
     * 输出：true
     * 示例 2：
     *
     * 输入：num = 14
     * 输出：false
     */
    public boolean isPerfectSquare(int num) {
        int left = 0, right = num;
        int res = -1;
        while (left <= right) {
            int mid = left + ((right - left) >> 2);
            if ((long)mid * mid < num) {//加long防止太长了越界
                left = mid + 1;
            } else if ((long)mid * mid > num)  {
                right = mid - 1;
            }else {
                return true;
            }
        }
        return false;
    }
}
